import collections
from typing import List


class Solution:
    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], target_path: List[str]) -> List[int]:
        graph = collections.defaultdict(set)
        for edge in roads:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])

        path1 = [[i] for i in range(n)]
        dp1 = [1 if names[i] != target_path[0] else 0 for i in range(n)]

        for name in target_path[1:]:
            path2 = [[] for _ in range(n)]
            dp2 = [float("inf")] * n

            for i in range(n):
                v1 = 1 if names[i] != name else 0
                for j in graph[i]:
                    v2 = dp1[j] + v1
                    if v2 < dp2[i]:
                        dp2[i] = v2
                        path2[i] = path1[j] + [i]

            path1 = path2
            dp1 = dp2

        ans_val, ans_path = float("inf"), []
        for i in range(n):
            if dp1[i] < ans_val:
                ans_val = dp1[i]
                ans_path = path1[i]

        return ans_path


if __name__ == "__main__":
    # [0,2,4,2]
    print(Solution().mostSimilar(n=5, roads=[[0, 2], [0, 3], [1, 2], [1, 3], [1, 4], [2, 4]],
                                 names=["ATL", "PEK", "LAX", "DXB", "HND"], target_path=["ATL", "DXB", "HND", "LAX"]))

    # [0,1,0,1,0,1,0,1]
    print(Solution().mostSimilar(n=4, roads=[[1, 0], [2, 0], [3, 0], [2, 1], [3, 1], [3, 2]],
                                 names=["ATL", "PEK", "LAX", "DXB"],
                                 target_path=["ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX"]))

    # [3,4,5,4,3,2,1]
    print(Solution().mostSimilar(n=6, roads=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]],
                                 names=["ATL", "PEK", "LAX", "ATL", "DXB", "HND"],
                                 target_path=["ATL", "DXB", "HND", "DXB", "ATL", "LAX", "PEK"]))
